package ejercicios;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import interfaces.tests.CountWaysToProduceGivenAmountOfMoney;

public class CountWaysToProduceGivenAmountOfMoneyImpl implements CountWaysToProduceGivenAmountOfMoney{
	public int countWaysToProduceGivenAmountOfMoney(int cents) {
    	return helperCountWaysToProduceMoney(cents, new ArrayList<Integer>(), 0);
    }
    
    public int helperCountWaysToProduceMoney(int cents, List<Integer> combination, int lastSearch){
    	int[] options = {1, 5, 10, 25, 50};
    	int count = 0;
    	List<Integer> newCombination;
    	
    	for (;lastSearch < options.length; lastSearch++){
    		if (currentAmmount(combination)+options[lastSearch] == cents){
    			return count+1;
    		}
    		if (currentAmmount(combination)+options[lastSearch] > cents){
    			return count;
    		}
    		
    		newCombination = new LinkedList<Integer>(combination);
    		newCombination.add(options[lastSearch]);
    		
    		count += helperCountWaysToProduceMoney(cents, newCombination, lastSearch);
    	}
    	return count;
    }
    
    public int currentAmmount(List<Integer> combination){
    	int ammount = 0;
    	for (int current : combination){
			ammount += current;
		}
    	return ammount;
    }
}